package com.fengdi.everyday.hard;

public class MinNumberOperations {
    class Interval {
        int begin;
        int end;
    }

    public int minNumberOperations(int[] target) {
        /*
        * TODO
        *  1. 每次完整遍历一遍数组，在每次遍历中都将target中的每个元素减少1，循环退出的条件是数组中的数字全部为0
        *
        * */

        int ans = 0;
        while(!this.isAllZero(target)) {
            // 找到一个没有0的连续区间
            //该区间内的值全部-1
            this.decrease(target, this.getInterval(target));
            ans++;
        }
        return ans;
    }

    private boolean isAllZero(int[] target) {
        for(int x : target) {
            if(x != 0) return false;
        }
        return true;
    }

    private Interval getInterval(int[] target) {
        Interval interval = new Interval();
        interval.begin = 0;
        interval.end = target.length - 1;
        // 找到首个非0元素
        for(int i = 0; i < target.length; i++) {
            if(target[i] != 0) {
                interval.begin = i;
                break;
            }
        }

        // 找到该连续段的结尾
        for(int i = interval.begin + 1; i < target.length; i++) {
            if(target[i] == 0) {
                interval.end = i - 1;
                break;
            }
        }

        return interval;
    }

    private void decrease(int[] target, Interval interval) {
        for(int i = interval.begin; i <= interval.end; i++) {
            target[i] -= 1;
        }
    }
}
